package leetcode.graph.course;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 207. 课程表
 * 是否可能完成所有课程的学习
 *
 * 课程号是  0 ~ numCourses-1
 *
 */
public class CanFinish {

    public static void main(String[] args) {
        CanFinish solution = new CanFinish();
        int[][] prerequisites = {{1, 0}, {0, 1}};

        boolean res = solution.canFinish(2, prerequisites);
        System.out.println(res);
    }

    // 图结构对象
    List<List<Integer>> edges;

    // 访问标识数组
    // 0没访问  1访问中 2已完成
    int[] visited;

    // 是否可以完成所有课程的学习
    // 是否构成闭环
    boolean valid = true;

    /**
     * @param numCourses    课程数量
     * @param prerequisites 课程表先后顺序
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 初始化图结构
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            // 给图中添加节点
            edges.add(new ArrayList<>());
        }
        // 默认是都是0
        visited = new int[numCourses];

        // 寻找每个课程的下个课程列表(对应多个课程)
        for (int[] info : prerequisites) {
            // List的序号对应课程号
            // [ai, bi], 表示如果要学习课程 ai, 则必须先学习课程bi, bi —> ai
            // 给每个节点设置相邻节点列表 注意这边是有向图
            edges.get(info[1]).add(info[0]);
        }

        // 再对每个课程进行遍历
        for (int i = 0; i < numCourses && valid; ++i) {
            // 当前课程没访问
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    /**
     * 深度优先遍历 检查是否构成环
     *
     * @param courseNo 当前课程号
     */
    public void dfs(int courseNo) {
        // 设置为访问中
        visited[courseNo] = 1;
        for (int v : edges.get(courseNo)) {
            // 如果相邻节点为访问, 递归进行访问
            if (visited[v] == 0) {
                // 递归访问
                dfs(v);
                // 访问完毕之后 如果valid为false, 表示存在闭环, 直接返回
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                // 构成闭环 直接返回
                valid = false;
                return;
            }
        }
        // 设置为已完成
        visited[courseNo] = 2;
    }


    /**
     * 广度优先遍历
     *
     * @param numCourses    课程数量
     * @param prerequisites 课程表先后顺序
     * @return
     */
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        // 初始化图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            graph.add(new ArrayList<>());
        }

        // 各个节点的入度
        int[] inDegree = new int[numCourses];
        for (int[] info : prerequisites) {
            graph.get(info[1]).add(info[0]);
            // 对应节点的入度加1
            inDegree[info[0]]++;
        }

        // 使用队列存储入度为0的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            // 入度为0的课程号入队
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 访问的课程数量
        int visited = 0;
        while (!queue.isEmpty()) {
            ++visited;
            int u = queue.poll();
            for (int v : graph.get(u)) {
                // 相邻节点的入度减1
                inDegree[v]--;
                // 入度为 0的节点入队
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 判断访问的课程数量是否相等
        return visited == numCourses;
    }
}
